package arithmetic.LeetCode;

import java.util.LinkedList;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 * https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&id=top-100-liked
 * @author jiangfeng on 2023/4/17
 */
public class LargestRectangleArea {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.largestRectangleArea(new int[]{2,1,2}));
    }
    static class Solution {

        public int largestRectangleArea(int[] heights) {
            int result =0;
            // 单调栈来找下一个比自己小的元素位置.
            LinkedList<Integer> stack =new LinkedList();
            // 一个技巧:两边加上两个为0的哑节点(哨兵sentinel节点),不影响结果.可以省去判空逻辑
            int[] newHeights = new int[heights.length+2];
            for(int i=1;i<heights.length;i++){
                newHeights[i]=heights[i];
            }
            stack.push(0);
            for(int i=1;i<newHeights.length;i++){
                while(newHeights[stack.peek()]>newHeights[i]){
                    // 开始触发出栈操作时,计算一下栈里的最大值.
                    int j = stack.pop();
                    int wights = i-stack.peek()-1;
                    result=Math.max(result,wights*newHeights[j]);
                }
                stack.push(i);
            }
            return result;
        }


        // 单调增栈 ,以高为突破口!
        public int largestRectangleArea4(int[] heights) {
            int result =0;
            // 单调栈来找下一个比自己小的元素位置.
            LinkedList<Integer> stack =new LinkedList();
            for(int i=0;i<heights.length;i++){
                while(!stack.isEmpty() && heights[stack.peek()]>heights[i]){
                    // 开始触发出栈操作时,计算一下栈里的最大值.
                    int j = stack.pop();
                    int wights = stack.isEmpty()?i:i-stack.peek()-1;
                    result=Math.max(result,(wights)*heights[j]);
                }
                stack.push(i);
            }
            // 最后出栈时,右边界一定是到顶了.
            int i=heights.length;
            while(!stack.isEmpty()){
                int j = stack.pop();
                // 栈元素为空时,左边界到顶了
                int wights = stack.isEmpty()?i:i-stack.peek()-1;
                // 计算一下最大值
                result=Math.max(result,heights[j]*(wights));
            }
            return result;
        }


        // 单调栈.和动态规划
        // 单调增栈
        public int largestRectangleArea3(int[] heights) {
            int result = 0;
            // 单调栈来找下一个比自己小的元素位置.
            LinkedList<Integer> stack = new LinkedList();
            for (int i = 0; i < heights.length; i++) {
                if (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                    // 开始触发出栈操作时,计算一下栈里的最大值.
                    // 从i,到栈低的那个
                    int l = stack.getLast();
                    int r = i;
                    while (l <= r) {
                        int min = 0;
                        if (heights[l] > heights[r]) {
                            min = heights[r];
                            result = Math.max(result, (r - l + 1) * min);
                            r--;
                        } else {
                            min = heights[l];
                            result = Math.max(result, (r - l + 1) * min);
                            l++;
                        }
                    }
                    // 清掉
                    stack.clear();
                }
                stack.push(i);
            }
            int i = 0;
            while (!stack.isEmpty()) {
                int d = stack.pop();
                i++;
                // 计算一下最大值
                result = Math.max(result, heights[d] * i);
            }
            return result;
        }

        public int largestRectangleArea2(int[] heights) {
            int result = 0;
            // 先暴力法,以高为主
            for(int i=0;i<heights.length;i++){
                int l=i-1;
                while(l>=0&& heights[l]>=heights[i]){
                    l--;
                }
                int r=i+1;
                while(r<heights.length&& heights[r]>=heights[i]){
                    r++;
                }
                result=Math.max(result,heights[i]*(r-l+1));
            }
            return result;
        }


        public int largestRectangleArea1(int[] heights) {
            // 有个题,离他最近的最大值.
            int result = 0;
            // pb[n] =
            // 先暴力法
            for (int i = 0; i < heights.length; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = i; j < heights.length; j++) {
                    min = Math.min(min, heights[j]);
                    result = Math.max(result, min * (j - i + 1));
                }
            }
            return result;
        }
    }
}
